package com.ryujung.linked_list.leetCode_82;

import com.ryujung.linked_list.node.ListNode;
/*
 * @lc app=leetcode.cn id=82 lang=java
 *
 * [82] 删除排序链表中的重复元素 II
 *
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/description/
 *
 * algorithms
 * Medium (47.35%)
 * Likes:    262
 * Dislikes: 0
 * Total Accepted:    43.4K
 * Total Submissions: 91.6K
 * Testcase Example:  '[1,2,3,3,4,4,5]'
 *
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 *
 *
 * 示例 2:
 *
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 *
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

/**
 * 注意给定的是排序链表，
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode pos = head;
        //记录重复的值，初始值为  链表的最小值-1。
        int duplicate = head.val - 1;
        while (pos != null) {

            if ((pos.val == duplicate || pos.next != null && pos.val == pos.next.val)) {
                //有重复的元素，记录重复的值，pos指针下移，pre指针不做任何动作，
                duplicate = pos.val;
                pos = pos.next;
            } else {
                //跳过重复或没有重复，将pre指向pos，并将两个指针同时下移
                pre.next = pos;
                pre = pos;
                pos = pos.next;
            }
        }
        //如果链表最后是重复元素，pre还要手动置为null，否则pre将指向重复的元素
        pre.next = null;

        return dummy.next;
    }

    /**
     * 2023年02月01日14:59:39追加
     * 思路：
     * 已排序的单向链表，需要保存重复元素之前的元素，以及当前重复中的首个元素，
     * 遇到重复元素，直接将两个重复元素删除，并保留重复值，然后继续往下遍历，
     * 遇到与重复值相同的节点，直接删掉继续遍历
     */
    public static ListNode deleteDuplicates2(ListNode head) {
        ListNode pre = new ListNode(0, head);
        ListNode beforeRepeat = pre;
        ListNode cur = head;

        // -100 <= Node.val <= 100 确保默认值不会和链表的值相同
        int repeatVal = -101;
        while (cur != null) {
            ListNode next = cur.next;
            if (cur.val == repeatVal) {
                cur = next;
                beforeRepeat.next = cur;
                continue;
            }
            if (next == null) break;

            if (cur.val == next.val) {
                repeatVal = cur.val;
                cur = next.next;
                beforeRepeat.next = cur;
            } else {
                beforeRepeat = cur;
                cur = next;
            }
        }
        return pre.next;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)

    public static void main(String[] args) {
        ListNode result = deleteDuplicates2(new ListNode(1, 2, 3, 3, 4, 4, 5));
        System.out.println(result);
    }
}
// @lc code=end
